/*
 * @lc app=leetcode.cn id=654 lang=golang
 * @lcpr version=30118
 *
 * [654] 最大二叉树
 */

// @lcpr-template-start

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// @lcpr-template-end
// @lc code=start

func constructMaximumBinaryTree(nums []int) *TreeNode {
	if len(nums) == 1 {
		return &TreeNode{Val: nums[0]}
	}
	if len(nums) == 0 {
		return nil
	}

	imax := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] > nums[imax] {
			imax = i
		}
	}

	root := &TreeNode{Val: nums[imax]}
	root.Left = constructMaximumBinaryTree(nums[:imax])
	root.Right = constructMaximumBinaryTree(nums[imax+1:])
	return root
}

// @lc code=end

/*
// @lcpr case=start
// [3,2,1,6,0,5]\n
// @lcpr case=end

// @lcpr case=start
// [3,2,1]\n
// @lcpr case=end

*/
